package leetcode101.data_structure;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @class Code13
 * @description 128. 最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 *  
 *
 * 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * 示例 2：
 *
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 *  
 *
 * 提示：
 *
 * 0 <= nums.length <= 104
 * -109 <= nums[i] <= 109
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-14 8:25
 */
public class Code13 {
    public static void main(String[] args) {
        int[] nums = new int[]{100,4,200,1,3,2};
        System.out.println(longestConsecutive(nums));
    }

    public static int longestConsecutive(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        if (nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1, o2);
            }
        });

        for (int i : nums) {
            set.add(i);
        }

        List<Integer> list = new ArrayList<>(set);
        int res = 1, begin = 0, end = 1;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) == list.get(i - 1) + 1) {
                end += 1;
            } else {
                res = Math.max(end - begin, res);
                begin = i;
                end = i + 1;
            }
        }
        return Math.max(end - begin, res);
    }
}
/*
将所有的数字放进一个treeSet当中并从小到大排序
然后将treeSet的所有数据放进list中，然后遍历list即可求解
 */